<html>
  <head>
	  <meta http-equiv="content-type" content="text/html; charset=utf-8" />
    <title>i5ting_ztree_toc:线性表（一）</title>
		<link href="toc/style/github-bf51422f4bb36427d391e4b75a1daa083c2d840e.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/style/github2-d731afd4f624c99a4b19ad69f3083cd6d02b81d5.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/css/zTreeStyle/zTreeStyle.css" media="all" rel="stylesheet" type="text/css"/>
	  <style>
		pre {
		    counter-reset: line-numbering;
		    border: solid 1px #d9d9d9;
		    border-radius: 0;
		    background: #fff;
		    padding: 0;
		    line-height: 23px;
		    margin-bottom: 30px;
		    white-space: pre;
		    overflow-x: auto;
		    word-break: inherit;
		    word-wrap: inherit;
		}

		pre a::before {
		  content: counter(line-numbering);
		  counter-increment: line-numbering;
		  padding-right: 1em; /* space after numbers */
		  width: 25px;
		  text-align: right;
		  opacity: 0.7;
		  display: inline-block;
		  color: #aaa;
		  background: #eee;
		  margin-right: 16px;
		  padding: 2px 10px;
		  font-size: 13px;
		  -webkit-touch-callout: none;
		  -webkit-user-select: none;
		  -khtml-user-select: none;
		  -moz-user-select: none;
		  -ms-user-select: none;
		  user-select: none;
		}

		pre a:first-of-type::before {
		  padding-top: 10px;
		}

		pre a:last-of-type::before {
		  padding-bottom: 10px;
		}

		pre a:only-of-type::before {
		  padding: 10px;
		}

		.highlight { background-color: #ffffcc } /* RIGHT */
		</style>
  </head>
  <body>
	  <div>
				<div style='width:25%;'>
						<ul id="tree" class="ztree" style='width:100%'>

						</ul>
				</div>
        <div id='readme' style='width:70%;margin-left:20%;'>
          	<article class='markdown-body'>
            	<h1 id="-">线性表（一）</h1>
<h3 id="26-"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/">26、删除有序数组中的重复项</a></h3>
<p>给你一个有序数组 <code>nums</code> ，请你<strong><a href="http://baike.baidu.com/item/原地算法"> 原地</a></strong> 删除重复出现的元素，使每个元素 <strong>只出现一次</strong> ，返回删除后数组的新长度。</p>
<p>不要使用额外的数组空间，你必须在 <strong><a href="https://baike.baidu.com/item/原地算法">原地 </a>修改输入数组</strong> 并在使用 O(1) 额外空间的条件下完成。</p>
<p><strong>说明:</strong></p>
<p>为什么返回数值是整数，但输出的答案是数组呢?</p>
<p>请注意，输入数组是以<strong>「引用」</strong>方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。</p>
<p>你可以想象内部操作如下:</p>
<pre><code>// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i &lt; len; i++) {
    print(nums[i]);
}
</code></pre><h5 id="-1-"><strong>示例 1：</strong></h5>
<pre><code>输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
</code></pre><h5 id="-2-"><strong>示例 2：</strong></h5>
<pre><code>输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
</code></pre><hr>
<h5 id="-">解法</h5>
<p>思路：双指针，右指针在排序数组中遍历，当遇到当前位置的值与上一个位置的值不同时，即第一次出现，则把值赋予left指针所在的位置</p>
<pre><code class="lang-java">class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len &lt;= 1){
            return len;
        }

        int left = 0;

        for(int right = 1; right &lt; len; right ++){
            if(nums[right] != nums[right - 1]){
                nums[++left] = nums[right];
            }
        }
        return left + 1;

    }
}
</code></pre>
<h3 id="80-ii"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/">80. 删除有序数组中的重复项 II</a></h3>
<p>给你一个有序数组 <code>nums</code> ，请你<strong><a href="http://baike.baidu.com/item/原地算法"> 原地</a></strong> 删除重复出现的元素，使每个元素 <strong>最多出现两次</strong> ，返回删除后数组的新长度。</p>
<p>不要使用额外的数组空间，你必须在 <strong><a href="https://baike.baidu.com/item/原地算法">原地 </a>修改输入数组</strong> 并在使用 O(1) 额外空间的条件下完成。</p>
<h5 id="-1-"><strong>示例 1：</strong></h5>
<pre><code>输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
</code></pre><h5 id="-2-"><strong>示例 2：</strong></h5>
<pre><code>输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
</code></pre><hr>
<h5 id="-">解法</h5>
<p>思路：同样是双指针，right指针遍历数组，当right所在位置的值不等于left所在位置-2上的值，则说明right所在位置的值是第一次出现或第二次出现。</p>
<p>left指代的是right位置上的值在数组中的位置最后出现的位置，故left - 2的值与right值相等则说明已经出现了2次以上</p>
<pre><code class="lang-java">class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len &lt;= 2){
            return len;
        }

        int left = 2;

        for(int right = 2; right &lt; len ; right++){
            if(nums[right] != nums[left - 2] ){
                nums[left ++ ] = nums[right];
            }
        }
        return left;
    }
}
</code></pre>
<h3 id="33-"><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/">33. 搜索旋转排序数组</a></h3>
<p>整数数组 <code>nums</code> 按升序排列，数组中的值 <strong>互不相同</strong> 。</p>
<p>在传递给函数之前，<code>nums</code> 在预先未知的某个下标 <code>k</code>（<code>0 &lt;= k &lt; nums.length</code>）上进行了 <strong>旋转</strong>，使数组变为 <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code>（下标 <strong>从 0 开始</strong> 计数）。例如， <code>[0,1,2,4,5,6,7]</code> 在下标 <code>3</code> 处经旋转后可能变为 <code>[4,5,6,7,0,1,2]</code> 。</p>
<p>给你 <strong>旋转后</strong> 的数组 <code>nums</code> 和一个整数 <code>target</code> ，如果 <code>nums</code> 中存在这个目标值 <code>target</code> ，则返回它的下标，否则返回 <code>-1</code> 。</p>
<h5 id="-1-"><strong>示例 1：</strong></h5>
<pre><code>输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
</code></pre><h5 id="-2-"><strong>示例 2：</strong></h5>
<pre><code>输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
</code></pre><h5 id="-3-"><strong>示例 3：</strong></h5>
<pre><code>输入：nums = [1], target = 0
输出：-1
</code></pre><hr>
<h5 id="-">解法</h5>
<p>思路：二分法，从中间分段则左右两边一定有一边是有序的，用二分判断。</p>
<ol>
<li><p>首先target大于mid上的值，直接返回mid</p>
</li>
<li><p>否则判断left的值是否小于等于right的值</p>
<p>是的话：</p>
<ul>
<li>target小于nums[mid]且大于等于nums[left]，则目标一定在左边</li>
<li>否则在右边</li>
</ul>
<p>否的话：</p>
<ul>
<li>target小于等于nums[right]且target大于nums[mid]，则目标一定是在右边</li>
<li>否则的话在左边</li>
</ul>
</li>
</ol>
<pre><code class="lang-java">class Solution {
    public int search(int[] nums, int target) {

        if(nums.length == 0){
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;
        while(left &lt;= right){
            int mid = left + (( right - left ) &gt;&gt; 1);
            if(target == nums[mid]){
                return mid;
            }else if(nums[left] &lt;= nums[mid]){
                if(target &lt; nums[mid] &amp;&amp; target &gt;= nums[left]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(target &lt;= nums[right] &amp;&amp; target &gt; nums[mid]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
</code></pre>

          	</article>
        </div>
		</div>
  </body>
</html>
<script type="text/javascript" src="toc/js/jquery-1.4.4.min.js"></script>
<script type="text/javascript" src="toc/js/jquery.ztree.all-3.5.min.js"></script>
<script type="text/javascript" src="toc/js/ztree_toc.js"></script>
<script type="text/javascript" src="toc_conf.js"></script>

<SCRIPT type="text/javascript" >
<!--
$(document).ready(function(){
    var css_conf = eval(markdown_panel_style);
    $('#readme').css(css_conf)
    
    var conf = eval(jquery_ztree_toc_opts);
		$('#tree').ztree_toc(conf);
});
//-->
</SCRIPT>